# -*- coding: utf-8 -*-

'''
@author: 5822 - Duarte Marques & 5955 - João Rosa
@date: 06 de Junho de 2013
@obs: Trabalho de Estruturas de Dados e Algoritmos
      Docente: Prof. Jasnau Caeiro
'''

import math
import sys

class heapsort:
	'''
	Classe que contém o algoritmo HeapSort.
	'''

	def __init__(self, A):
		'''
		Metodo onde inicializam algumas variaveis para
		serem utilizadas mais tarde.
		Recebe como parameto uma lista "A".
		'''
		self.A = A
		self.i = 1

	def max_heapify(self, A, i):
		'''
		Metodo que faz a troca de posição dos valores
		para que vão ficando por ordem.
		'''

		global heapsize
		left = 2 * i 
		right = 2 * i + 1

		if left <= heapsize and self.A[left] > self.A[i]:
			largest = left
		else:
			largest = i

		if right <= heapsize and self.A[right] > self.A[largest]:
			largest = right

		if largest != i:
			self.A[i], self.A[largest] = self.A[largest], self.A[i]
			self.max_heapify(self.A, largest)

	def build_max_heap(self, A):
		'''
		Metodo que envia os valores para o metodo "max_heapify",
		para que sejam trocados de posição.
		'''
		for i in range(int(math.floor(len(self.A)/2)), 0, -1):
			self.max_heapify(self.A, i)

	def heapsort(self):
		'''
		Metodo que recebe uma lista para ordenar, e procura
		o valor mais alto para a partir desse ir ordenando.
		'''
		global heapsize
		heapsize = len(self.A)-1
		self.build_max_heap(self.A)
		for i in range (len(self.A)-1, 1, -1):
			self.A[1], self.A[i] = self.A[i], self.A[1]
			heapsize = heapsize - 1
			self.max_heapify(self.A, 1)
		return self.A

# A = [sys.maxint,16,4,10,14,7,9,3,2,8,1]
# B = [sys.maxint,4,1,3,2,16,9,10,14,8,7]
# B = [sys.maxint,450,500,550,150,200,250,300,350,400,750,800,600,650,700,1,50,100,850,900,950,1000,1050]
# print B


# g = heapsort(B)
# print g.heapsort()
